\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage{amssymb}
\usepackage{verbatim}
\usepackage{indentfirst}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{xeCJK}
\usepackage{float}
\usepackage{listings}
\usepackage{graphicx} % Required for figures
\usepackage{subcaption} % Required for subfigures
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\begin{document}
% =================================================
\title{Numerical Analysis Programming Homework \# 2}

\author{周川迪 3220101409}
\affil{强基数学2201}

\date{\today}

\maketitle

\begin{abstract}
  This report covers the implementation and analysis of Newton interpolation, Hermite interpolation, and Bezier curve interpolation. Each method is discussed in detail, including design, implementation, and results. Through experiments, the effects of different point distributions on interpolation accuracy are observed, particularly the Runge phenomenon and the stabilization effect of Chebyshev nodes.
\end{abstract}



\section{Introduction}
Interpolation is a fundamental technique in numerical analysis, allowing the approximation of complex functions based on sampled data. This report implements three interpolation methods: Newton interpolation, Hermite interpolation, and Bezier curve interpolation. These techniques are applied to various problems to examine their characteristics and limitations.



\section{Problem A: Design of Newton, Hermite, and Bezier Curve Interpolation}
I used doxygen to generate design documentation. Go to \texttt{./Doxydocs/html/index.html}



\section{Promblem B-F: Applications of Interpolation}
\subsection{Problem B: Runge Phenomenon with Equally Spaced Points}
Using Newton interpolation for $f(x) = \frac{1}{1 + x^2}$ on $x \in [-5, 5]$ with equally spaced points, oscillations near the endpoints illustrate the Runge phenomenon. As shown in Figure \ref{fig:B_plot}, oscillations become more pronounced with larger $n$ values, indicating instability in high-degree polynomial interpolation.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.75\textwidth]{images/B_plot.png}
    \caption{Interpolation Results for Problem B: Runge Phenomenon with Equally Spaced Points}
    \label{fig:B_plot}
\end{figure}



\subsection{Problem C: Chebyshev Nodes and Improved Stability}
Using Chebyshev nodes for $f(x) = \frac{1}{1 + 25x^2}$ on $x \in [-1, 1]$, oscillations observed with equally spaced points were significantly reduced. As seen in Figure \ref{fig:C_plot}, interpolation with Chebyshev nodes avoids wide oscillations (avoids Runge phenomenon), confirming their stabilizing effect.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.75\textwidth]{images/C_plot.png}
    \caption{Interpolation Results for Problem C: Stability with Chebyshev Nodes}
    \label{fig:C_plot}
\end{figure}



\subsection{Problem D: Application of Hermite Interpolation}

In this problem, Hermite interpolation is applied to estimate the position and velocity of a car based on given data points that include time, position, and velocity. The Hermite polynomial was constructed using both the position and velocity data to ensure that the curve passes through the specified points while also matching the slope at those points.

The results in \texttt{output\_D.txt} :

\begin{itemize}
  \item Problem (a): At \( t = 10 \) seconds
  \item Position is \( 742.503 \) feet
  \item Velocity is \( 48.3817 \) feet per second
  \item Problem (b):
  \item The car EXCEEDS the speed limit of \( 81 \) feet per second at \( t = 6 \) seconds.
\end{itemize}




\subsection{Problem E: Predicting Larvae Survival}
The Newton interpolation method was employed to model the growth curves of two larvae samples. The predictions in \texttt{output\_E.txt} for their survival after 28 days are as follows:
\begin{itemize}
  \item Sample 1 is not predicted to die after 28 days.
  \item Sample 2 is not predicted to die after 28 days.
\end{itemize}

Figure \ref{fig:E_plot} illustrates the weight trajectories of both samples. It can be seen that after the 28th day, the average weight of larvae in both groups significantly increased, with the weight of Sample 1 reaching an order of $10^4$ on the 43rd day. This is clearly inconsistent with intuitive and actual phenomena, mainly due to the insufficient information provided by the interpolation points, which results in a larger error in the interpolation polynomial. 

In this case, using the least squares method may be better.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.75\textwidth]{images/E_plot.png}
    \caption{Interpolation results for Problem E: Weight Growth Curve Prediction}
    \label{fig:E_plot}
\end{figure}



\subsection{Problem F: Heart Curve Approximation with Bezier Curves}
Using cubic Bezier curves for different values of $m$, a heart shape was approximated with increasing accuracy. Figure \ref{fig:F_plots} presents the results for $m = 10, 40, 160$, showing that higher values yield smoother and more accurate approximations.


\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.3\textwidth}
      \includegraphics[width=\textwidth]{images/F_10_plot.png}
      \caption{$m = 10$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
      \includegraphics[width=\textwidth]{images/F_40_plot.png}
      \caption{$m = 40$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
      \includegraphics[width=\textwidth]{images/F_160_plot.png}
      \caption{$m = 160$}
  \end{subfigure}
  \caption{Interpolation results for Problem F: Heart shape approximation with Bezier curves}
  \label{fig:F_plots}
\end{figure}

\subsubsection*{Discussion for Problem F}
Cubic B\'ezier curves are commonly used for curve fitting, approximating a curve $\gamma:(0,1) \rightarrow \mathbb{R}^D$ with specified tangent vectors $\gamma'$. However, when the number of marker points, $m$, is large, each B\'ezier segment becomes shorter. While $\gamma'$ is relatively large, this often results in control points far from the segment, leading to undesirable "spikes" in the output.

When I was stucked, a roommate suddenly had an idea of adjusting the tangent vectors by a factor positively correlated with $m$. This adjustment effectively reduces the distance between the control points and the curve, minimizing the spikes. Following this implementation, the generated B\'ezier curves exhibited improved smoothness and accuracy, confirming the effectiveness of the proposed solution.

\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.45\textwidth}
      \includegraphics[width=\textwidth]{Correction.png}
      \caption{$Adjustment \ from \ the \  textbook$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.45\textwidth}
      \includegraphics[width=\textwidth]{Failure_160.png}
      \caption{$Previous \ Algorithm,\ m=160$}
  \end{subfigure}
  \caption{Interpolation results for Problem F: Heart shape approximation with Bezier curves}
  \label{fig:F_corrections}
\end{figure}

\section*{Acknowledgements}
1. Numerical Analysis textbooks and online resources such as \href{https://www.csdn.net/}{CSDN} and \href{https://www.zhihu.com/}{Zhihu} for algorithm references and theoretical guidance. 

2. My roommate Wang Zi in our NA class, giving important ideas about problem F.

3. \href{https://kimi.moonshot.cn}{Kimi AI} for additional coding assistance. 

4. \href{https://chat.openai.com}{ChatGPT} (GPT-4) for code completion and debugging. 

\end{document}